package com.algorithm.example.hash;

import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * <h2>哈希表<h2/>
 * <p>给每份数据分配一个编号，放入表格（数组）</p>
 * <p>建立编号瑜表格索引的关系，将来就可以通过编号快速查找数据</p>
 * <ol>
 *     <p>1.理想情况编号当唯一，数组能容纳所有数据</p>
 *     <p>2.现实是不能说为了容纳所有数据造一个超大数组，编号也有可能重复</p>
 * </ol>
 * 解决
 * <ol>
 *     <P>1.有限长度的数组，以【拉链 -> 数组 + 链表】方式存储数据</P>
 *     <p>2.允许编号适当重复，通过数据自身来进行区分</p>
 * </ol>
 *
 * @author lzt
 * @version 1.0
 * @since 2024/2/27 21:26
 */
public class HashTable {

    // 节点类
    static class Entry {
        /**
         * 哈希值
         */
        int hash;

        /**
         * 键
         */
        Object key;

        /**
         * 值
         */
        Object value;

        /**
         * 下一个节点
         */
        Entry next;

        public Entry(int hash, Object key, Object value, Entry next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public Entry(int hash, Object key, Object value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }

    Entry[] table = new Entry[16];
    int size = 0; // 元素个数
    float loadFactor = 0.75f;
    int threshold = (int) (table.length * loadFactor);


    /* 求模运算替换为位运算
        - 前提：数组长度是 2 的 n 次方
        - hash % 数组长度 等价于 hash & (数组长度-1)
     */


    /**
     * 根据hash码获取value
     */
    Object get(int hash, Object key) {
        int idx = hash & (table.length - 1);
        if (table[idx] == null) {
            return null;
        }
        Entry p = table[idx];
        while (p != null) {
            if (p.key.equals(key)) {
                return p.value;
            }
            p = p.next;
        }
        return null;
    }

    /**
     * 向hash表存入新key value 如果key重复，则更新
     */
    void put(int hash, Object key, Object value) {
        int idx = hash & (table.length - 1);
        if (table[idx] == null) {
            table[idx] = new Entry(idx, key, value);
        }

        Entry p = table[idx];
        while (true) {
            if (p.key.equals(key)) {
                p.value = value;
                return;
            }
            if (p.next == null) {
                break;
            }
            p = p.next;
        }
        p.next = new Entry(hash, key, value);
        size++;
        if (size > threshold) {
            resize();
        }
    }

    /**
     * 扩容
     */
    private void resize() {
        Entry[] newTable = new Entry[table.length * 2];
        for (int i = 0; i < table.length; i++) {
            Entry p = table[i];
            if (table[i] != null) {

                Entry a = null;
                Entry b = null;
                Entry aHead = null; // 新分裂头节点
                Entry bHead = null; // 新分裂头节点

                while (p != null) {
                    if ((p.hash & table.length) == 0) {
                        // a链表
                        if (a != null) {
                            a.next = p;
                        } else {
                            aHead = p;
                        }
                        a = p;
                    } else {
                        // b链表
                        if (b != null) {
                            b.next = p;
                        } else {
                            bHead = p;
                        }
                        b = p;
                    }
                    p = p.next;
                }

                if (a != null) {
                    newTable[i] = aHead;
                    a.next = null;
                }

                if (b != null) {
                    newTable[i + table.length] = bHead;
                    b.next = null;
                }
            }
        }
        table = newTable;
        threshold = (int) (table.length * loadFactor);
    }

    /**
     * 根据hash值删除，返回删除值
     */
    Object remove(int hash, Object key) {
        int idx = hash & (table.length - 1);


        Entry p = table[idx];
        Entry parent = null;
        while (p != null) {
            if (p.key.equals(key)) {
                if (parent == null) {
                    table[idx] = p.next;
                } else {
                    parent.next = p.next;
                }
                size--;
                return p.value;
            }
            parent = p;
            p = p.next;

        }
        return null;
    }

    public void put(Object key,Object value) {
        int hash = getHash(key);
        put(hash,key,value);
    }

    public Object get(Object key) {
        int hash = getHash(key);
        return get(hash,key);
    }

    public Object remove(Object key) {
        int hash = getHash(key);
        return remove(hash,key);
    }

    private static int getHash(Object key) {
        return key.hashCode();
    }

    public void print() {
        int[] sums = new int[table.length];
        for (int i = 0; i < table.length; i++) {
            Entry p = table[i];
            while (p != null) {
                sums[i]++;
                p = p.next;
            }
        }
//        System.out.println(Arrays.toString(sums));

        Map<Integer, Long> collect = Arrays.stream(sums).boxed().collect(Collectors.groupingBy(e -> e, Collectors.counting()));
        System.out.println(collect);
    }

}
